package other;

import java.util.Arrays;

public class smallPractice{
    static int i=0;

    public static int getMax(int[] arr){
        int temp = arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>temp){
                temp = arr[i];
            }
        }
        System.out.printf("Max:"+temp+"\n");
        return temp;
    }

    public static int[] selectSort(int[] arr){
        int[] arrcopy = Arrays.copyOf(arr,arr.length);
        int temp = 0;
        for(int i=0;i<arrcopy.length-1;i++){
            int index = i;
            for(int j=i+1;j<arrcopy.length;j++){
                if(arrcopy[index]>arrcopy[j]){
                    index = j;
                }
            }
            if(index != i){
                temp = arrcopy[index];
                arrcopy[index] = arrcopy[i];
                arrcopy[i] = temp;
            }

            System.out.print("第"+i+"次排序输出结果：");			//输出每步排序的结果
            for(int h=0;h<arrcopy.length;h++)
            {
                System.out.print(" "+arrcopy[h]);				//输出
            }
            System.out.print("\n");

        }
        return arrcopy;
    }

    public static int[] bubbleSort(int[] arr){
        int[] arrcopy = Arrays.copyOf(arr,arr.length);
        int temp= 0 ;
        for(int i=0;i<arrcopy.length-1;i++){
            for(int j=0;j<arrcopy.length-i-1;j++){
                if(arrcopy[j]>arrcopy[j+1]){
                    temp= arrcopy[j];
                    arrcopy[j]= arrcopy[j+1];
                    arrcopy[j+1]= temp;
                }
            }

            System.out.print("第"+i+"次冒泡排序：");
            for(int h=0;h<arrcopy.length;++h){
                System.out.print(" "+arrcopy[h]);
            }
            System.out.print("\n");
        }
        return arrcopy;
    }

    public static int[] insertSort(int[] arr){
        int[] arrcopy = Arrays.copyOf(arr,arr.length);

        for(int i=1;i<arrcopy.length;i++){
            int temp = arrcopy[i];
            int j = i-1;
            while(j>=0 && arrcopy[j]>temp){
                arrcopy[j+1] = arrcopy[j];
                j--;
            }
            arrcopy[j+1] = temp;

            System.out.print("第"+i+"次排序输出结果：");			//输出每步排序的结果
            for(int h=0;h<arrcopy.length;h++)
            {
                System.out.print(" "+arrcopy[h]);				//输出
            }
            System.out.print("\n");
        }
        return arrcopy;
    }

    public static int[] quickSort(int[] arr){
        int[] arrcopy = Arrays.copyOf(arr,arr.length);
        arrcopy = quickSortimplement(arrcopy,0,arrcopy.length-1);
        System.out.print("quickSortimplement排序输出结果：");			//输出每步排序的结果
        for(int h=0;h<arrcopy.length;h++)
        {
            System.out.print(" "+arrcopy[h]);				//输出
        }
        System.out.print("\n");
        return arrcopy;
    }

    private static int[] quickSortimplement(int[] arr, int low, int high) {
        int start=low;
        int end=high;
        int key=arr[low];
        while(start<end){
            while(start<end && arr[end]>=key){
                end--;
            }
            if(arr[end]<key){
                int temp = arr[end];
                arr[end] = key;
                arr[start] = temp;
            }

            System.out.print("第"+(++i)+"步排序结果:");			//输出每步排序的结果
            for(int h=low;h<(high+1);h++)
            {
                System.out.print(" "+arr[h]);				//输出
            }
            System.out.print("\n");


            while(start<end && arr[start]<=key){
                start++;
            }
            if(arr[start]>key){
                int temp = arr[start];
                arr[start] = key;
                arr[end] = temp;
            }
            System.out.print("第"+(++i)+"步排序结果:");			//输出每步排序的结果
            for(int h=low;h<(high+1);h++)
            {
                System.out.print(" "+arr[h]);				//输出
            }
            System.out.print("\n");
        }

        if(low<start) quickSortimplement(arr,low,start-1);
        if(end<high) quickSortimplement(arr,end+1,high);

        return arr;
    }


}
